/*
Largest Rectangle in Histogram Total Accepted: 41302 Total Submissions: 182466 My Submissions Question Solution
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].


The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.
*/
#include <iostream>
#include "print.h"
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;


/***/
//Definition for an interval.
struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};
class Solution {
public:
	int largestRectangleArea(vector<int>& height) {
		if (height.size() ==0)
		{
			return 0;
		}

		height.push_back(0);
		stack<int> stk;
		int i = 0;
		int maxArea = 0;

		while (i < height.size())
		{
			if (stk.empty() || height[stk.top()] <=height[i])
			{
				stk.push(i++);
			}
			else
			{
				int t = stk.top();
				stk.pop();
				int temp = height[t] * (stk.empty() ? i : i - stk.top() - 1);
				maxArea = max(maxArea, temp);
			}
		}

		return maxArea;
	}
};





int main()
{
	int a[] = { 2, 1, 5, 6, 2, 3 };
	vector<int> nums(a, a + sizeof(a) / sizeof(int));
	Solution s;

	int res = s.largestRectangleArea(nums);


	system("pause");
	return 0;
}